#include <iostream>
#include <stack>

using namespace std;

//implement queue with stack
template<class T>
class squeue
{
public:
	squeue(){}
	~squeue(){}
	void push(const T& v);
	void pop();
	T& front();
private:
	stack<T> iS;
	stack<T> oS;	
};

template<class T>
void squeue<T>::push(const T& v) //注意关于T的语法
{
	iS.push(v);
}

template<class T>
void squeue<T>::pop()
{
	if(!oS.empty())
		oS.pop();
	else
	{
		if(iS.empty())
			throw "no element in queue!";
		while(!iS.empty())
		{
			oS.push(iS.top());
			iS.pop();
		}
		oS.pop();
	}
}

template<class T>
T& squeue<T>::front()
{
	if(!oS.empty())
		return oS.top();
	if(iS.empty())
		throw "no front element in queue!";
	while(!iS.empty())
	{
		oS.push(iS.top());
		iS.pop();
	}
	return oS.top();
}


int main()
{
	squeue<int> Q;
	Q.push(1);
	Q.push(2);
	cout << Q.front() << " ";
	Q.pop();
	Q.push(3);
	cout << Q.front() << " ";
	Q.pop();
	Q.push(4);
	Q.push(5);
	cout << Q.front() << " ";
	Q.pop();
	cout << Q.front() << " ";
	Q.pop();
	cout << Q.front() << " ";
	Q.pop();
	try{
		Q.pop();
	}catch(...)
	{cout << "catched";}
	return 0;
}
